package demo.letcode.top100;

import java.util.ArrayList;
import java.util.List;

public class _46全排列_2 {
    public static void main(String[] args) {
        /**
         * abc
         * 全排列abc acb bac bca cab cba
         */
        String str = "eat";
        List<String> ret = new ArrayList<>();
        backtrack(str.toCharArray(), 0, ret);
        System.out.println(ret);
    }

    public static void backtrack(char[] chars, int start, List<String> ret) {
        if (start == chars.length) {
            ret.add(new String(chars));
            return;
        }
        // abc
        for (int i = start; i < chars.length; i++) {
            swap(chars, start, i); // 交换
            backtrack(chars, start + 1, ret); // 递归处理剩余部分
            swap(chars, start, i); // 回溯，恢复交换前的状态
        }
    }

    public static void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}
